package pro.softzhang.algo.lc200;

import pro.softzhang.algo.flag.knowledge.KSlidingWindow;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * 209. 长度最小的子数组
 * https://leetcode.cn/problems/minimum-size-subarray-sum
 */
@KSlidingWindow
public class LC209_MinimumSizeSubarraySum {
    public static void main(String[] args) {
        int target = 7;
        int[] nums = new int[]{2,3,1,2,4,3};
        int size = new Solution().minSubArrayLen(target, nums);
        System.out.println(size);
    }

    /**
     *
     */
    static
    class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int len = Integer.MAX_VALUE, sum = 0, left = 0;
            for (int right = 0; right < nums.length; right++) {
                sum += nums[right];
                while (left <= right && sum >= target) {
                    len = Math.min(len, right - left + 1);
                    sum -= nums[left];
                    left++;
                }
            }
            return len == Integer.MAX_VALUE ? 0 : len;
        }
    }

    @XOptimal
    static
    class Solution1 {
        public int minSubArrayLen(int target, int[] nums) {
            int res = nums.length + 1, sum = 0, left = 0;
            for (int right = 0; right < nums.length; right++) {
                sum += nums[right];
                while (sum >= target) {
                    res = Math.min(res, right - left + 1);
                    sum -= nums[left];
                    left++;
                }
            }
            return res <= nums.length ? res : 0;
        }
    }
}
